class Solution {
public:
    int countDigitOne(int n) {
        if(n < 1)  return 0;
        /*
		若是采用循环实现，将会是O(nlogn)的时间复杂度，若数字很大时时间复杂度过高；
		我们发现每次统计时8,9，56，987等这些数字里面没有'1'，而'1'以1、11、12、13...100，101等有一定规律的
		形式出现，因此我们可以猜测'1'的出现次数是有规律可循的；
        时间复杂度为O(logn)的算法：举例发现'1'在不同的数位上出现次数的规律与n的关系;
        每次去掉最低位进行递归;
        1.当前数字位是'1'时，该位'1'出现的次数n_copy*multiple + behindNum + 1;
        2.当前数位是'0'时，该位'1'出现的次数n_copy*multiple;
        3.当前数位是其他情况时，该位'1'出现的次数(n_copy + 1)*multiple
        */
        int sum = 0;//'1'总共出现的次数
        int behindNum = 0;//当前数字后面的所有数字
        long multiple = 1;//乘数，个位数的时候为1，每统计进一位，就*10(可能会超出int范围)
        int n_copy = n;//代表去掉最低位后的剩余数字
        int remain = n % 10;//余数

        while(n_copy){
            n_copy /= 10;
            //当前位是1时,该位'1'出现的个数由它后面的数与前面的数共同决定
            if(remain == 1){
                if(n_copy > 0) sum += n_copy * multiple;
                sum += behindNum + 1;
            }else if(remain == 0){
                sum += n_copy * multiple;//最起码出现过n_copy*multiple次
            }else{
                sum += ((n_copy + 1) * multiple);
            }
            behindNum += (remain * multiple);
            multiple *= 10;
            remain = n_copy % 10;
        }

        return sum;
    }
};